package sort;

/**
 * Created by Hyman on 2017/3/23.
 */
public class QuichSort {

    public static void main(String[] args) {

        int[] arr = {5, 3, 6, 8, 4};
        sortArray(arr);

        for(int i : arr) {
            System.out.print(i + " ");
        }
    }


    public static int[] sortArray(int[] arr) {
        quickSort(arr, 0, arr.length-1);
        return arr;
    }

    private static void quickSort(int[] arr, int low, int high) {
        if(low < high) {
            int pivot = partition(arr, low, arr.length-1);
            //int pivot = partition2(arr, low, arr.length-1);
            quickSort(arr, low, pivot-1);
            quickSort(arr, pivot+1, arr.length-1);
        }
    }

    private static int partition(int[] arr, int low, int high) {

        int pivot = arr[low];

        while(low < high) {

            while(low < high && arr[high] >= pivot) {
                high--;
            }
            arr[low] = arr[high];

            while(low < high && arr[low] <= pivot) {
                low++;
            }
            arr[high] = arr[low];
        }

        arr[low] = pivot;
        return low;
    }

    private static int partition2(int[] arr, int low, int high) {

        int dest = low;
        int pivot = arr[low];
        int tmp = 0;

        for(int pointer = low+1; pointer <= high; pointer++) {
            if(arr[pointer] < pivot) {
                dest++;
                tmp = arr[dest];
                arr[dest] = arr[pointer];
                arr[pointer] = tmp;
            }
        }

        tmp = arr[dest]; // 将基准元素插入到最终位置
        arr[dest] = pivot;
        arr[low] = tmp;

        return dest;
    }
}
